package leetcode;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2021-12-07 23:47
 **/
public class LeetCode1034 {

    public int[][] colorBorder(int[][] grid, int row, int col, int color) {

        int n = grid.length;
        int m = grid[0].length;
        // 如果给的点的值等于要着的颜色 可以直接返回 因为根据题意 只有与给定点的颜色相同才有被判定为边界的资格。一旦颜色相同了 边界的颜色就是color 所以可以直接返回了  但是该条件可要可不要
        if (grid[row][col] == color) {
            return grid;
        }

        boolean[][] visited = new boolean[n][m];
        dfs(grid, row, col, grid[row][col], visited, color, n, m);

        return grid;

    }

    public void dfs(int[][] grid, int i, int j, int col, boolean[][] visited, int target, int n, int m){
        // 如果下标越界 或者 与初始点的值不相同 或者 该点被访问过 都不能成为边界
        if (i > n-1 || i < 0 || j > m-1 || j < 0 || grid[i][j] != col || visited[i][j]) {
            return;
        }

        visited[i][j] = true;
        boolean border = false;

        // 之前已经判断过condition下标没有越界
        // 其次，如果是grid的边界，那么一定是连通的边界
        // 最后，如果该点的任意一个方向不为初始点的值，那么该点肯定是位于边界上的，因为如果不是边界，四面的值都应该是val
        if (i == 0 || j == 0 || j == m-1 || i == n-1 || grid[i+1][j] != col || grid[i-1][j] != col || grid[i][j-1] != col || grid[i][j+1] != col) {
            border = true;
        }

        // dfs四个方向
        dfs(grid, i+1, j, col, visited, target, n, m);
        dfs(grid, i-1, j, col, visited, target, n, m);
        dfs(grid, i, j+1, col, visited, target, n, m);
        dfs(grid, i, j-1, col, visited, target, n, m);

        if (border) {
            grid[i][j] = target;
        }

    }

}
